/*
	Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
	Note:
	You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. 
	The number of elements initialized in nums1 and nums2 are m and n respectively.
*/
#include <string.h>
void merge(int* nums1, int m, int* nums2, int n) {
    int i = 0, j = 0, k = 0;
    int all[m + n];
    while(i < m && j < n){
    	if(nums1[i] <= nums2[j] ){
	    	all[k++] = nums1[i++];
	    }else{
	    	all[k++] = nums2[j++];
    	}
    }
    
    if( i == m && j != n){//此时的话nums1的元素全部插入， 
    	memcpy(all+k, nums2+j, (n-j)*sizeof(int)); 
    }else if(i != m){
    	memcpy(all+k, nums1+i, (m-i)*sizeof(int)); 
    }
    memcpy(nums1, all, (m+n)*sizeof(int)); 
}

int main(){
	int nums1[4] = {1,3,5,7};
	int nums2[4] = {2,4,6,8};
	merge(nums1, 4, nums2, 4);
	int i;
	for(i = 0 ; i < 4 + 4 ; i++){
		printf("%d ", nums1[i]);
	}
	return 0;
}


void merge(int* nums1, int m, int* nums2, int n) {
	int i = m - 1, j = n - 1, k = m + n - 1;
	while(i >= 0 && j >= 0){
		nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
	}
	//谁先到0的问题i先到0，拷贝j，j先到0万事ok
	while(j >= 0){
		nums1[k--] = nums2[j--];
	} 
}